This Phase II/III randomized, open-label study will evaluate the safety and efficacy of combined immunotherapy with subcutaneous (SQ) Interleukin-2 (IL-2) and histamine dihydrochloride versus SQ Il-2 alone in patients with advanced malignant melanoma. Survival, time-to-progression, tumor response, duration of response, disease-free survival, and quality of life measures will be evaluated.